package Others;

public class _481_MagicalString {
    //over time limited
    public int magicalString_0(int n) {
        String s = "122";
        int i = 2;
        int len = 3;
        while (len < n) {
            int times = s.charAt(i++) - '0';
            String cha = String.valueOf((Character.getNumericValue(s.charAt(times - 1)) ^ 3));
            len += times;
            for (int j = 0; j < times; j++) {
                s += cha;
            }
        }
        int count = 0;
        String subs = s.substring(0, n);
        for (char c : subs.toCharArray()) {
            if (c == '1') {
                count++;
            }
        }
        return count;
    }

    public int magicalString(int n) {
        int[] magic = new int[n];
        int slow = 0, fast = 0, num = 1, count = 0;
        while (fast < n) {
            magic[fast++] = num;
            count += num & 1;
            if (fast < n && magic[slow++] == 2) {
                magic[fast++] = num;
                count += num & 1;
            }
            num ^= 3;
        }
        return count;
    }
}
